package com.yun.algorithmproblem.leetcode;

public class Leetcode3479 {

    public static void main(String[] args) {
        Leetcode3479 obj = new Leetcode3479();
        int[] fruits = new int[]{4, 2, 5};
        int[] baskets = new int[]{3, 5, 4};
        System.out.println(obj.numOfUnplacedFruits(fruits, baskets));
    }

    public int numOfUnplacedFruits(int[] fruits, int[] baskets) {
        int n = baskets.length;
        SegmentTree segmentTree = new SegmentTree(baskets);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int pos = segmentTree.queryFirstGreaterOrEqual(fruits[i]);
            if (pos == -1) {
                ans++;
            } else {
                segmentTree.updateToZero(pos);
            }
        }
        return ans;
    }

    public static class SegmentTree {
        int[] segmentTree;
        int size;
        int n;

        public SegmentTree(int[] data) {
            n = data.length;
            size = 1;
            while (size < n) {
                size <<= 1;
            }
            this.segmentTree = new int[size * 2];

            System.arraycopy(data, 0, segmentTree, size, n);

            for (int i = size - 1; i > 0; i--) {
                segmentTree[i] = Math.max(segmentTree[2 * i], segmentTree[2 * i + 1]);
            }
        }

        public int queryFirstGreaterOrEqual(int val) {
            if (segmentTree[1] < val) {
                return -1;
            }
            return findFirst(1, val);
        }

        private int findFirst(int cur, int val) {
            if (cur >= size) {
                if (cur < size * 2 && segmentTree[cur] >= val) {
                    return cur;
                } else {
                    return -1;
                }
            }

            int left = cur * 2;
            if (segmentTree[left] >= val) {
                int leftRes = findFirst(left, val);
                if (leftRes != -1) {
                    return leftRes;
                }
            }

            int right = cur * 2 + 1;
            if (segmentTree[right] >= val) {
                return findFirst(right, val);
            }

            return -1;
        }

        public void updateToZero(int pos) {
            if (pos < size || pos >= n + size) {
                return;
            }
            // 定位到叶子节点
            segmentTree[pos] = 0;

            // 向上更新父节点，同时判断是否需要继续
            pos >>= 1; // 移动到父节点
            while (pos > 0) {
                int oldMax = segmentTree[pos];
                int newMax = Math.max(segmentTree[2 * pos], segmentTree[2 * pos + 1]);

                // 如果父节点的最大值没有变化，说明更上层节点也不会变，直接退出
                if (oldMax == newMax) {
                    break;
                }

                segmentTree[pos] = newMax;
                pos >>= 1; // 继续向上更新
            }
        }
    }
}
